 

  #include "ge_evo.h"
  #include "../mylib.h"
  
  
  Node **nodes_ptr_ptr[MAX_NODES_PTR];
  /* Gli elementi di quest'array contengono puntatori a puntatori di nodi e
     viene utilizzato per memorizzare tutti i puntatori a puntatori di tut-
     ti i nodi del secondo individuo di input che contengono lo stesso sim-
     bolo del nodo scelto dal primo individuo. Dopo che tutti questi nodi
     sono stati memorizzati (dalla procedura Node::add_not_terms) uno di
     essi viene scelto in maniera casuale per lo scambio con il primo nodo.
     */

  
  
  /******************************************************************
          Dichiarazione delle variabili esterne al file.
  ******************************************************************/

  extern Grammar grammar;
  /* E' la dichiarazione della variabile grammar che si trova nel
     file main e che contiene la grammatica utilizzata. */



  /******************************************************************
          Definizione delle procedure della classe GE_INDIVIDUAL
  ******************************************************************/



  /*
  ----------------- procedura ge_Individual ------------------------------
  *** Scritta il:
  E' la procedura che costruisce la lista di alberi dell'individuo e che 
  scrive il relativo fenotipo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void ge_Individual::build_list()
  {
     int trees_num, i;
       
          
     /* Si genera un numero casuale tra il minimo e il massimo numero di 
        elementi che la lista può contenere. */
     trees_num = rnd(MIN_TREES, MAX_TREES);
     
               
     // Si genera la lista di alberi              
     for (i=0; i < trees_num; ++i)
        trees_list.push_back(Tree(grammar.start_symbol()));
       

     // Si chiama la procedura per la scrittura del fenotipo.
     write_pheno();
  
       
     return;
  }
  /*
  ----------------- procedura ge_Individual ------------------------------
  *** Scritta il:
  E' la procedura che costruisce la lista di alberi dell'individuo e che 
  scrive il relativo fenotipo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void ge_Individual::build_list(int a, int b)
  {
     int trees_num, i;
     //cout<<endl<<a<<" "<<b;
          
     /* Si genera un numero casuale tra il minimo e il massimo numero di 
        elementi che la lista può contenere. */
     trees_num = rnd(a, b);
     
                         
     // Si genera la lista di alberi              
     for (i=0; i < trees_num; ++i)
        trees_list.push_back(Tree(grammar.start_symbol()));
       

     // Si chiama la procedura per la scrittura del fenotipo.
     write_pheno();
  
       
     return;
  }
  
  /*
  ----------------- procedura ge_Individual ------------------------------
  *** Scritta il:
  E' la procedura costruttrice della classe utilizzata per costruire la co-
  pia di un individuo gia' esistente. Inizializza solo i parametri, ma non
  costruisce l'albero di derivazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  ge_Individual::ge_Individual()
  {
     register int i;

     // Si inizializza il fenotipo dell'individuo.
     for (i=0; i < MAX_CHAR_PHENOTYPE; ++i)
        phenotype[i] = '\0';
     
     
     return;      
  }



  /*
  ----------------- procedura kill-----------------------------------------
  *** Scritta il:
  E' la procedura di tipo virtuale che serve a cancellare l'albero di deri-
  vazione dell'indiivduo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void ge_Individual::kill()
  {
     register list<class Tree>::iterator tree_iter; 
     
    
     /* Si cancellano tutti gli alberi di derivazione presenti nell'indivi-
        duo.  */
     for (tree_iter=trees_list.begin(); tree_iter != trees_list.end(); 
          ++tree_iter)   
        tree_iter->del_tree();
     
     trees_list.clear();
     
        
      /*char str[10000];
      cout<<endl<<"ind killed, nodes: "<<comp_nodes_num();*/
     
      // Si cancella se stessi.
     delete this;
     
     return;
  }

  /*
  ----------------- procedura write_pheno ----------------------------------
  *** Scritta il:
  E' la procedura che scrive il fenotipo dell'individuo. Essa chiama la pro-
  cedura che visita l'albero per effettuare quest'operazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void ge_Individual::write_pheno()
  {
     register int i;
     int max_char_pheno;
     register list<class Tree>::iterator tree_iter;
     char *pheno_ptr; 
   
     /* Si inizializza il fenotipo e lo si punta con una variabile tempora-
        nea. */ 
     for (i=0; i < MAX_CHAR_PHENOTYPE; ++i)
        phenotype[i] = '\0'; 
     pheno_ptr = phenotype;
           
     /* Si inizializza il massimo numero di caratteri che pu� essere con-
        tenuto nel fenotipo. */
     max_char_pheno = MAX_CHAR_PHENOTYPE;
        
     /* Si scandisce la lista di alberi dell'individuo e se ne costruisce 
        il fenotipo, chiamando la procedura che visita gli alberi di deri-
        vazione e ne restituisce la stringa contenuta. */
     for (tree_iter = trees_list.begin(); tree_iter != trees_list.end(); 
          ++tree_iter)
        // Si controlla se c'e' ancora spazio nel fenotipo.
        if (max_char_pheno > 1)  
          tree_iter->give_string(pheno_ptr, max_char_pheno);
        /* Altrimenti si stampa un messaggio di warning e si UCCIDE l'indi-
           viduo. */
        else
        { 
          cout<<"*";           
          alive = false;
        }    


     return;	      
  }
  
  /*
  ----------------- procedura comp_nodes_num ------------------------------
  *** Scritta il:
  Calcola il numero totale di nodi presenti negli alberi dell'individuo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */ 
  int ge_Individual::comp_nodes_num()
  {
     int tmp_nodes;
     register list<class Tree>::iterator tree_iter;
     
     // Inizializzazione
     tmp_nodes = 0;
     
     
     // Si scandisce la lista di alberi dell'individuo. 
     for (tree_iter = trees_list.begin(); tree_iter != trees_list.end(); 
          ++tree_iter)
        tmp_nodes += tree_iter->comp_N_nodes();
     
     
     // si memorizza il numero di nodi appena calcolato
     nodes_num = tmp_nodes;
             
     
     return tmp_nodes;        
  }  
  
   
  /*
  ----------------- procedura update --------------------------------
  *** Scritta il:
  Aggiorna i parametri dell'oggetto chiamando le funzioni appropriate.
  *** Ultima modifica: ore 16.00 del 04/04/03
  
  void ge_Individual::update()
  {
   
     // Si riscrive il fenotipo dell'individuo.                   
     write_pheno();

     // Si ricalcola la fitness.
     comp_fitness();

     
     return;
  }   

  
  
  /******************************************************************
          Definizione delle procedure della classe TREE
  ******************************************************************/

   /*
  ----------------- procedura TREE ----------------------------------------
  *** Scritta il:
  E' la procedura costruttrice, effettua solo l'inizilizzazione dei parame-
  tri.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Tree::Tree()
  {
     register int i;

     // Si inizializzano gli attributi.
     N_nodes = 0;
     root = NULL_NODE;


  }



  /*
  ----------------- procedura Tree ----------------------------------------
  *** Scritta il:
  E' la procedura costruttrice della classe. Costruisce un nuovo albero
  partendo dal simbolo passato come parametro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Tree::Tree(char symbol)
  {  
     /* Si genera l'albero con il node radic econ il simbolo uguale a quel-
        lo passato come parametro. */
     root = new Node(symbol);

     
     return;
  }
  
  
  /*
  ----------------- procedura Tree ----------------------------------------
  *** Scritta il:
  E' un'altra procedura costruttrice della classe, e' un costruttore di co-
  pie. E' utilizzata per costruire copie di liste di alberi.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */

  
  Tree::Tree(const Tree &right_tree)
  {
     // Si inizializzano gli attributi dell'albero.
     N_nodes = right_tree.N_nodes;


     // Si costruisce la copia dell'albero.
     root = right_tree.root->build_copy();

    
     return;
  }



  /*
  ----------------- procedura del_tree-------------------------------------
  *** Scritta il:
  E' la procedura che restituisce alla memoria gli oggetti della classe No-
  de utilizzati per costruire l'albero.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Tree::del_tree()
  {
     root->del_node();
     
      

     return;
  }



  /*
  ----------------- procedura choose_not_term -----------------------------
  *** Scritta il:
  Questa procedura sceglie in maniera casuale un nodo non terminale dell'al-
  bero e restituisce come valore il puntatore al puntatore del nodo scelto,
  il quale si trova nel nodo padre del nodo scelto.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node **Tree::choose_not_term()
  {
     int rnd_num, times;
     Node **tmp_ptr;

     times = 0;

     /* Si esegue un ciclo per evitare che, se la scelta cade su un figlio
        non terminale del nodo radice, venga ritornato il valore NULL. */
     do
     {
       rnd_num = rnd(1, N_nodes);

       // E'stato scelto proprio il nodo radice.
       if (rnd_num == 1)
         return &root;

       /* Si chiama la procedura che restituisce il nodo corrispondente a
          a rnd_num. */
       tmp_ptr = root->find_not_term(rnd_num);
     }
     while((tmp_ptr == NULL_NODE_PTR) && (times++ < 10));


     return tmp_ptr;
  }
  /*
  ----------------- procedura extract_symbol ------------------------------
  *** Scritta il:
  Estrae dall'alberoo un nodo che contiene il simbolo passato come parame-
  tro scegliendolo in maniera casuale tra tutti i nodi dell'albero che con-
  tengono quel simbolo. Restituisce come valore il puntatore al puntatore
  del nodo scelto, il quale si trova nel nodo padre del nodo scelto. Se quel
  simbolo non e' contenuto nell'individuo a procedura restituisce il valore
  nil.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node **Tree::extract_symbol(char symbol)
  {
     int  nodes_found, random_int;


     /* Si controlla che il nodo da estrarre non sia il nodo radice.
     */

     if (symbol == grammar.start_symbol())
       return &root;

     nodes_found = 0;

    /* La procedura che segue trova, in maniera ricorsiva, tutti i
       nodi dell'individuo che contengono il carattere passato come
       parametro e li memorizza nell'array di puntatori di puntatori
       dell'oggetto della classe crossover. Inoltre, essa memorizza
       nel secondo parametro passato il numero di nodi trovati. */
     root->add_not_terms(symbol, nodes_found);

     /* Se non vengono trovati nodi si restituisce NULL. */
     if (nodes_found == 0)
       return NULL_NODE_PTR;
     // Altrimenti si sceglie in maniera casuale uno dei nodi trovati.
     else random_int = rnd(0, nodes_found - 1);
         return nodes_ptr_ptr[random_int];
  }
  

  /*
  ----------------- procedura give_string ----------------------------------
  *** Scritta il:
  Visita l'albero per scrivere la stringa codificata nell'albero, chiamando
  la procedura visit_tree della classe Node e calcola il numero di nodi pre-
  senti nell'albero  e la sua massima profondita'. Il parametro e' la stringa 
  in cui scrivere la stringa codificat< dall'albero, il secondo il numero di 
  caratteri ancora disponibile nella stringa. 
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Tree::give_string(char* &string, int &aval_chars)
  {

     char *str_ptr;
     register int i;

          
     /* Si inizializza il numero di nodi presenti e la profondita' dell'albe-
        ro. */
     N_nodes = 0;	

	
     // Si inizializza il puntatore alla stringa.
     str_ptr = string;

     /* Si chiama la procedura ricorsiva della classe Node che effettua i
        calcoli necessari. */
     N_nodes = root->visit_node(string, aval_chars);
     
     // Si termina il fenotipo con il "tappo".
     // *str_ptr = '\0'; 
     *string = '\0';
    
     return;
  }

  
  /*
  ----------------- procedura print_tree ----------------------------
  *** Scritta il:
  Stampa sul video l'albero di derivazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Tree::print_tree()
  {
     int i, max_depth;

     
     max_depth = root->comp_depth();
     printf("\n Albero di derivazione:\n");
     printf(" La sua profondita' massima e': %d\n", max_depth);
     for (i=0; i <= max_depth; ++i)
     {
        printf("livello %d: ", i);
        root->print_nodes(i);
        getchar();
        printf("\n");
     }
     printf("\n L'albero di derivazione e' terminato.\n");

     return;
  }
  
  /*
  ----------------- procedura comp_N_nodes ----------------------------
  *** Scritta il:
  Conta i nodi dell'albero.
  */ 
  
  int Tree::comp_N_nodes()
  {
      if (root != 0)
        return root->comp_nodes();
      else return 0;
  
  }

  
  /*
  --------------- OVERLOADING dell'operatore di assegnamento --------------
  *** Scritta il:
  Effettua l'overloading dell'operaore di assegnamento.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Tree Tree::operator=(const Tree &right_tree)
  {
     // Si inizializzano gli attributi dell'albero.
     N_nodes = right_tree.N_nodes;


     // Si costruisce la copia dell'albero.
     root = right_tree.root->build_copy();

    
     return *this;
  }
  /*
  --------------- Operatore di confronto --------------
  *** Scritta il:
  Effettua l'overloading dell'operaore di assegnamento.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  bool Tree::operator<(const Tree &right_tree)
  {
    if (label < 0) 
      return false;
    
    // Si controlla se l'altro albero è labellato oppure no
     if ((right_tree.label < 0 ) || (label < right_tree.label))
       return true;
     else return false;     
  }

  /******************************************************************
          Definizione delle procedure della classe NODE
   ******************************************************************/

  /*
  ----------------- procedura Node ----------------------------------------
  *** Scritta il:
  Questa procedura e' la generatrice della classe ed e' di tipo ricorsivo.
  Istanzia un nodo che possiede come simbolo quello passato come parametro,
  se il simbolo e' non terminale, la procedura chiede alla grammatica l'ap-
  plicazione relativa a quel simbolo e richiama se stessa per generare un
  numero di figli pari al numero di caratteri contenuti nella stringa otte-
  nuta dalla grammatica.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node::Node(char ch)
  {
     register int i;
     int N;
     char chunk[MAX_CHAR_CHUNK];
     register Node *temp_ptr;
     


    
     // Fase di inizializzazione.
     for (i=0; i < MAX_CHAR_CHUNK; ++i)
        chunk[i] = '\0'; 
     symbol = '\0';
     clause_num = 0;
     for (i=0; i < MAX_SONS; ++i)
        sons[i] = NULL_NODE;
     N = 0;
     
     // Costruzione del nodo.     
     symbol = ch; // Symbol e' un attributo della classe.

     if (grammar.not_terminal(ch))
     { 
       clause_num = grammar.give_string(ch, N, chunk);
       N_sons = N;


       /* Si controlla se la lunghezza del chunk e' maggiore del numero
          massimo di figli disponibili. */
       if (strlen(chunk) > MAX_SONS)
         abort_message("La lunghezza del chunk %s e' maggiore del numero \
         massimo di figli disponibili.", chunk);

       for (i=0; i < N_sons; ++i)
          sons[i] = new Node(chunk[i]);
     }
     else if (grammar.terminal(ch)) 
            N_sons = 0;
	  else abort_message("ERRORE nella creazione di un nuovo nodo!");
  }


  /*
  ----------------- procedura Node ----------------------------------------
  *** Scritta il:
  Questa procedura e' la generatrice della classe utilizzata dall'operatore
  Mutation  e' anch'essa di tipo ricorsivo. Istanzia un nodo che possiede
  come simbolo quello passato come primo parametro, il secondo parametro,
  invece, specifica quale clausola NON bisogna scegliere per continuare la
  generazione dell'albero.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node::Node(char ch, int not_choose)
  {
     register int i;
     int N;
     char chunk[MAX_CHAR_CHUNK];
     register Node *temp_ptr;

     // Fase di inizializzazione.
     for (i=0; i < MAX_CHAR_CHUNK; ++i)
        chunk[i] = '\0'; 
     symbol = '\0';
     clause_num = 0;
     for (i=0; i < MAX_SONS; ++i)
        sons[i] = NULL_NODE;
     N = 0;

     // Costruzione del nodo.     
     symbol = ch; // Symbol e' un attributo della classe.
     if (grammar.not_terminal(ch))
     { 
       clause_num =
       grammar.give_string(ch, N, chunk);//, not_choose);
       N_sons = N;
       for (i=0; i < temp_ptr->N_sons; ++i)
          sons[i] = new Node(chunk[i]);
     }
     else if (grammar.terminal(ch)) 
            N_sons = 0;
	  else abort_message("ERRORE nella creazione di un nuovo nodo!");
   
     return;
  }


  /*
  ----------------- procedura Node ----------------------------------------
  *** Scritta il:
  E' una terza procedura costruttrice della classe ed e' utilizzata per
  costruire le copie degli alberi di derivazione degli individui. E' anch'
  essa di tipo ricorsivo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node::Node()
  {
     register int i;
     register Node* temp_ptr;

     for (i=0; i < MAX_SONS; ++i)
        sons[i] = NULL_NODE;

     N_sons = 0;
     symbol = '\0';
     clause_num = 0;

     return;
  }

  /*
  ----------------- procedura del_node ------------------------------------
  *** Scritta il:
  In pratica, e' la procedura distruttrice della classe. Se ci sono nodi
  figli richiama se stesso ricorsivamente per ognuno dei figli, dopodiche'
  distrugge tutti i figli.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Node::del_node()
  {
     register int i;

     for (i=0; i < N_sons; ++i)
        // Chiama ricorsivamente la procedura su ognuno dei figli.
        sons[i]->del_node();

     // Cancella se stesso.
     delete this;


     return;
  }
  /*
  ----------------- procedura del_Node ------------------------------------
  *** Scritta il:
  E' una diversa procedura distruttrice della classe. Questa, diversamente
  dall'altra, possiede un parametro che e' un puntatore ad un nodo, esso
  rappresenta la radice della parte di albero che non si vuole eliminare.
  Tale procedura prima di effettuare la chiamata ricorsiva controlla se il
  nodo che si sta per eliminare e' quello passato come parametro, in tal
  caso non effettua la chiamata. Serve per la nuova mutazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Node::del_Node(Node * good_node_ptr)
  {
     register int i;

     for (i=0; i < N_sons; ++i)
        /* Si controlla che quel figlio non sia proprio quello da NON 
	       eliminare. In caso contrario chiama ricorsivamente la proce-
	       dura su ognuno dei figli */
        if (sons[i] != good_node_ptr)
          sons[i]->del_Node(good_node_ptr);

     return;
  }


  /*
  ----------------- procedura build_copy ----------------------------
  *** Scritta il:
  Questa procedura costruisce una copia del nodo a cui appartiene e
  ricorsivamente chiama se stessa su tutti i figli del nodo a cui ap-
  partiene. Essa restituisce il puntatore al nodo copia costruito.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node *Node::build_copy()
  {
    register Node *copy_ptr; 
    register int i;

      
    copy_ptr = new Node();

    copy_ptr->symbol = symbol;
    copy_ptr->N_sons = N_sons;

    // La procedura richiama se stessa per tutti i figli del nodo.
    for (i=0; i < N_sons; ++i)        
         copy_ptr->sons[i] = sons[i]->build_copy();
 

    return copy_ptr;
  }

  /*
  ----------------- procedura find_not_term -------------------------
  *** Scritta il:
  Questa procedura e'di tipo ricorsivo e trova il nodo corrispondente
  al numero N passato come parametro visitando l'albero depth-first.
  Se il nodo corrispondente e'terminale restituisce il nodo padre di
  quest'ultimo.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node **Node::find_not_term(int &N)
  {
     int i;
     Node **temp_node_ptr_ptr;


     // Decrementa di uno il numero di nodi da visitare.
     --N;

     /* Il prossimo passo controlla se si e' giunti ad un nodo termi-
        nale oppure al nodo cercato. */
     if ((N > 0) && (N_sons > 0))
       for (i=0; i < N_sons; ++i)
       {
          temp_node_ptr_ptr = sons[i]->find_not_term(N);

          /* Se la chiamata ritorna un valore diverso da NULL vuol
             dire che e' stato trovato il nodo cercato e bisogna ri-
             tornare il puntatore del puntatore ad esso. */
          if (temp_node_ptr_ptr != NULL_NODE_PTR)
            return temp_node_ptr_ptr;

          /* In caso contrario, si controlla se comunque il conteggio
             dei nodi e' arrivato a zero e se il figlio puntato con-
             tiene un nodo non terminale, in tal caso si ritorna il
             puntatore del puntatore ad esso.*/
          if (N == 0)
            if (grammar.not_terminal(sons[i]->symbol))
              return &sons[i];
            else break;
       }

     // Per tutti gli altri casi si ritorna il puntatore nullo.
     return NULL_NODE_PTR;
  }


  /*
  ----------------- procedura add_not_terms -------------------------
  *** Scritta il:
  Questa procedura e' di tipo ricorsivo e trova tutti i nodi che con-
  tengono il simbolo passato come parametro e ne memorizza il punta-
  tore al puntatore nell'array passato anch'esso come parametro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Node::add_not_terms (char symbol, int &next_free)
  {
     int i;

     // Se il nodo non contiene figli la procedura ritorna. 
     if (N_sons == 0)
       return;

     /* In  caso contrario controlla se i figli contengono il simbolo
        cercato. */
     else for (i=0; i < N_sons; ++i)
          {
             if (sons[i]->symbol == symbol)
             /* Se i figli contengono il simbolo cercato il puntatore
                al puntatore del nodo viene memorizzato nel prossimo
                elemento libero dell'array di puntatori di puntatori a
                nodi, che e' una struttura dati globale definita in
                ge_evo.h */
               nodes_ptr_ptr[next_free++] = &sons[i];

             /* La procedura viene chiamata ricorsivamente sui figli
                del nodo. */
             if (next_free == MAX_NODES_PTR)
             { 
	       printf("\n attenzione! durante un operazione di crossover\
                       il secondo individuo non e' stato visitato\
                       completamente perche' troppo  lungo");

              return;
             }
             sons[i]->add_not_terms(symbol, next_free);
          }

     return;
  }


  /*
  ----------------- procedura visit_node -----------------------------------
  *** Scritta il:
  Scrive aggiunge il simbolo contenuto nel nodo al fenotipo dell'individuo,
  inoltre incrementa il numero di nodi presenti nell'albero e la sua profon-
  dita'. Questa procedura e' di tipo ricorsivo  e restituisce il numero di 
  nodi dell'albero sottostante compreso se stesso. Il secondo parametro 
  indica il numero di caratteri ancora disponibile nella stringa passata 
  come primo parametro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  int Node::visit_node(char* &string_ptr, int &av_chars)
  {
     int i, sum;
    

     // Si inizializza il numero di nodi.
     sum = 1;
     
     // Se il nodo e' terminale viene scritto nel fenotipo. 
     if (grammar.terminal(symbol))
       // Si controlla se c'e' ancora spazio nella stringa. 
       if (av_chars > 1)
       {
         *string_ptr = symbol;
         ++string_ptr;
         
         // Si decrementa il numero di carattere disponibili.
         --av_chars;
       }
       // Se non c'e' piu' spazio si ritorna.
       else return sum;        
     /* Il simbolo contenuto e' un non terminale, si chiama la procedura
        sui figli. */
     else for (i=0; i < N_sons; ++i)             
             sum += sons[i]->visit_node(string_ptr, av_chars);
             

   return sum;
  }



  /*
  ----------------- procedura print_nodes ---------------------------
  ***  Scritta il:
  Stampa a video tutti i nodi della profondit� specificata come para-
  metro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Node::print_nodes(int depth)
  {
     int i;

     if (depth == 0)
     // E' stata raggiunta la profondita' cercata allora stampa.
       printf(" %c", symbol);
     else for (i=0; i < N_sons; ++i)
             sons[i]->print_nodes(depth - 1); 
     return;
  }

  /*
  ----------------- procedura comp_depth ----------------------------
  *** Scritta il:
  E' una procedura ricorsiva per il  calcolo della profondit� massima
  dell'albero sottostante.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  int Node::comp_depth()
  {
   int temp;
   register int i;

   temp = 0;

   /* Se il nodo possiede dei figli, calcola, in maniera ricorsiva,
      la profondit� massima sottostante. */
   if (N_sons)
   { 
     for (i=0; i < N_sons; ++i)
        if (sons[i]->comp_depth() > temp)
          temp = sons[i]->comp_depth();

     // Restituisce il numero di nodi calcolato.
     return temp + 1;
   }
   else return 0;//E' un nodo foglia ritorna il valore nullo.
  }
  
  /*
  ----------------- procedura comp_nodes ----------------------------
  *** Scritta il:
  E' una procedura ricorsiva per il  calcolo della profondit� massima
  dell'albero sottostante.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  int Node::comp_nodes()
  {
      int s, i;
      
      if (N_sons == 0)
          return 1;
      
      
      s = 0;
      
      for (i=0; i < N_sons; ++i)
         s += sons[i]->comp_nodes();
      
      
      return s;        
  }

  

  /*
  ----------------- procedura find_second_symbol -------------------
  *** Scritta il:
  Questa procedura cerca al di sotto del nodo un  secondo che con-
  tenga lo stesso simbolo di quello su cui e' chiamata la procedura
  e che si trovi alla profondita' (rispetto al nodo di parternza) 
  specificata dal parametro. Questa procedura serve ad implementare 
  la nuova versione della mutazione.
  ATTENZIONE!: questa regola vale solo per regole del tipo X->X...
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node *Node::find_second_symbol(int depth)
  { 
     int i;

     for (i=0; i < N_sons; ++i)
    	if (sons[i]->symbol == symbol)
	      if (depth == 1)
	        return sons[i];	  
          else return sons[i]->find_second_symbol(depth - 1);        
  
  
     return NULL_NODE; 
  }   
  

  /*
  ----------------- procedura find_deepest_symbol --------------------
  *** Scritta il:
  Questa procedura serve a trovare il puntatore del puntatore del nodo
  piu' profondo che contiene il simbolo passato come parametro. Questa 
  procedura serve ad implementare la nuova versione della mutazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Node **Node::find_deepest_symbol(char ch) 
  { 
     int i;
     Node **tmp_ptr;

     for (i=0; i < N_sons; ++i)
	if (sons[i]->symbol == ch)    
        {   
          tmp_ptr = sons[i]->find_deepest_symbol(ch);     
          if (tmp_ptr)
	    return tmp_ptr;
          else return &sons[i];	  
        }   

     return NULL_NODE_PTR; 
  }   

  /*
  ----------------- procedura mutation ------------------------------------
  *** Scritta il:
  Questa procedura e' di tipo ricorsivo ed implementa la mutazione multipla
  di un albero di mutazione. 
  derivazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Node::mutation(float prob)
  {     
     int i;
     char ch;
     

     // Si scandiscono i figli del nodo. 
     for (i=0; i < N_sons; ++i)
        // Si controlla che il figlio sia un non terminale.
        if (!grammar.terminal(sons[i]->symbol))
          if (prob)
          // ******* Il nodo viene mutato. *******
          {
            // Si memorizza il simbolo contenuto nel nodo scelto.
            ch = sons[i]->symbol;
            
            // Si elimina la parte sottostante al nodo scelto.
            delete sons[i];
            
            sons[i] = new Node(ch);//, clause);
          }
          else sons[i]->mutation(prob);
        
     
     

     return;
  }





  /************************************************************************
          Definizione delle procedure della classe CROSS_TREE
   ***********************************************************************/

  /*
  ----------------- procedura Cross_tree --------------------------------
  *** Scritta il:
  E' la procedura costruttrice della classe. E' vuota.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Cross_tree::Cross_tree()
  {
   return;
  }

  /*
  ----------------- procedura Cross_tree ----------------------------------
  *** Scritta il:
  E' la seconda procedura costruttrice della classe.  Inizializza la proba-
  bilita' di applicazione del crossover.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Cross_tree::Cross_tree(float prob_value)
  {
    prob = prob_value;


    return;
  }

  /*
  ----------------- procedura apply ---------------------------------------
  *** Scritta il:
  Questa procedura implementa l'operazione di crossover, applica l'operato-
  re di crossover ai primi due individui in input. La procedura costruisce
  due copie di questi individui  e vi applica l'operatore di crossover e
  restituisce i puntatori alle copie modificate nella seconda coppia di pa-
  rametri.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Cross_tree::apply(Individual *input_ptr_1, Individual *input_ptr_2,
                        Individual* &output_ptr_1,
                        Individual* &output_ptr_2)
  {
     /* Le due variabili sottostanti sono puntatori ai puntatori   nodi che
        vengono incrociati dal crossover e si trovano solo nei nodi padre
        del nodo che deve essere incrociato dal crossover.
     */
     Node **node_ptr_ptr_1, **node_ptr_ptr_2;
     Node *temp_node_ptr;
     register list<class Tree>::iterator tree_iter_1, tree_iter_2;
     int  tree_num, i;
     char ch;
     ge_Individual *ge_ptr_1, *ge_ptr_2; /* Questi puntatori servono per le
     chiamate di funzioni specifiche che si trovano in ge_Individual. */


     /* Si puntano gli individui in input con i puntatori ad oggetti della
     classe ge_Individual. Questa operazione deve essere fatta attraverso
     un casting!  */
     ge_ptr_1 = (ge_Individual *) input_ptr_1;
     ge_ptr_2 = (ge_Individual *) input_ptr_2;


     /* Si costruiscono le due copie degli individui ai quali applicare
        l'operatore di crossover. Il casting e' necessario poiche' build_
        copy restituisce un tipo Individual. */
     ge_ptr_1 = (ge_Individual *) ge_ptr_1->build_copy();
     ge_ptr_2 = (ge_Individual *) ge_ptr_2->build_copy();

     /* Si memorizzano i puntatori alle copie appena costruite nei parame
        tri di output. */
     output_ptr_1 = ge_ptr_1;
     output_ptr_2 = ge_ptr_2;
     
     // **** Si selezionano gli alberi a cui applicare il crossover. ****
     
     
     //cout<<endl<<ge_ptr_1->trees_list.size()<<flush;
     //  ************************** Individuo 1 *************************     
     // Si sceglie in maniera random un albero della lista.
     tree_num = rnd(0, ge_ptr_1->trees_list.size() - 1);
     
     //cout<<" t1: "<<tree_num<<flush;
     
     // Si punta l'albero scelto con un iteratore.
     for (tree_iter_1 = ge_ptr_1->trees_list.begin(), i=0; i < tree_num;
          ++i)
        ++tree_iter_1;      
     
    //  ************************** Individuo 2 *************************
     
    // Si sceglie in maniera random un albero della lista. 
    tree_num = rnd(0, ge_ptr_2->trees_list.size() - 1);

 
     // Si punta l'albero scelto con un iteratore.
     for (tree_iter_2 = ge_ptr_2->trees_list.begin(), i=0; i < tree_num;
          ++i)
        ++tree_iter_2;       


     // Si lancia la monetina ...
     if (flip(prob))
       /* Il crossover viene applicato agli alberi delle copie appena cos-
          truite. */
       cross(*tree_iter_1, *tree_iter_2);


     return;
  }

  /*
  ----------------- procedura cross ---------------------------------------
  *** Scritta il:
  Questa procedura implementa l'operazione di crossover, applica l'operato-
  re di crossover agli alberi passati come parametri.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Cross_tree::cross(Tree &tree_1, Tree &tree_2)
  {
     /* Le due variabili sottostanti sono puntatori ai puntatori   nodi che
        vengono incrociati dal crossover e si trovano solo nei nodi padre
        del nodo che deve essere incrociato dal crossover.
     */
     Node **node_ptr_ptr_1, **node_ptr_ptr_2;
     Node *temp_node_ptr;
     char ch;

     /* Si estrae in maniera casuale un nodo contenente un simbolo non ter-
        minale dal primo albero passato come parametro. Il nodo viene punta-
        to attraverso un puntatore al puntatore al nodo in questione che si
        trova nel suo nodo padre. Il simbol scelto viene restituito nel pa-
        rametro symbol passato alla funzione. */
     node_ptr_ptr_1 = tree_1.choose_not_term();

     /* Se non si riesce a scegliere un nodo non terminale dal primo indi-
        viduo, si lasciano i due individui in input inalterati. */
     if (node_ptr_ptr_1 == NULL_NODE_PTR)
       return;

     /* Si memorizza il simbolo contenuto nel nodo scelto. */
     ch = (*node_ptr_ptr_1)->symbol;

     /* Si inizializza l'array di puntatori a puntatori definito in
        ge_evo.h */
     ini_nodes_ptr_ptr();

     /* Si sceglie dal secondo input un nodo contenente lo stesso simbolo
        non terminale contenuto nel primo nodo scelto. */
     node_ptr_ptr_2 = tree_2.extract_symbol(ch);

     /* Se la funzione ritorna il puntatore nullo, vuol dire che il secon-
        do individuo non contiene nessun nodo con lo stesso simbolo del no-
        do scelto  dal primo individuo. In questo caso la procedura resti-
        tuisce i due individui inalterati. */
     if (node_ptr_ptr_2 == NULL_NODE_PTR)
       return;

     /* La coppia di nodi, sui due diversi individui, contenenti lo stesso
        simbolo e' stata trovata e quindi si puo' effettuare lo scambio. */
     else {
           temp_node_ptr = *node_ptr_ptr_2;
           *node_ptr_ptr_2 = *node_ptr_ptr_1;
           *node_ptr_ptr_1 = temp_node_ptr;
          }

     return;
  }


  /*
  ----------------- procedura ini_nodes_pt_ptr ----------------------------
  *** Scritta il:
  Inizializzazione dell'array nodes_ptr_ptr. Da utilizzare per l'operazione
  di crossover. Ricordiamo che quest'array e' definito nel file ge_evo.h e
  serve a puntare tutti i nodi presenti in un individuo che contengono un
  determinato simbolo.
  *** Ultima modifica: ore 16.00 del 04/04/03 
  */
  void Cross_tree::ini_nodes_ptr_ptr()
  {
   int i;

   for (i=0; i < MAX_NODES_PTR; ++i)
      nodes_ptr_ptr[i] = NULL_NODE_PTR;

   return;
  }
  
  
   /************************************************************************
          Definizione delle procedure della classe CROSS_LIST
   ***********************************************************************/

  /*
  ----------------- procedura Cross_list --------------------------------
  *** Scritta il:
  E' la procedura costruttrice della classe. E' vuota.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Cross_list::Cross_list()
  {
   return;
  }

  /*
  ----------------- procedura Cross_list ----------------------------------
  *** Scritta il:
  E' la seconda procedura costruttrice della classe.  Inizializza la proba-
  bilita' di applicazione del crossover.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Cross_list::Cross_list(float prob_value)
  {
    prob = prob_value;
    sorting = false;


    return;
  }

  /*
  ----------------- procedura Cross_list ----------------------------------
  *** Scritta il:
  E' la seconda procedura costruttrice della classe.  Inizializza la proba-
  bilita' di applicazione del crossover.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  Cross_list::Cross_list(float prob_value, bool s)
  {
    prob = prob_value;
    sorting = s;


    return;
  }

  /*
  ----------------- procedura apply ---------------------------------------
  *** Scritta il:
  Questa procedura implementa l'operazione di crossover, applica l'operato-
  re di crossover ai primi due individui in input. La procedura costruisce
  due copie di questi individui  e vi applica l'operatore di crossover e
  restituisce i puntatori alle copie modificate nella seconda coppia di pa-
  rametri.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Cross_list::apply(Individual *input_ptr_1, Individual *input_ptr_2,
                        Individual* &output_ptr_1,
                        Individual* &output_ptr_2)
  {       
     ge_Individual *ge_ptr_1, *ge_ptr_2; /* Questi puntatori servono per le
     chiamate di funzioni specifiche che si trovano in ge_Individual. */


     /* Si puntano gli individui in input con i puntatori ad oggetti della
     classe ge_Individual. Questa operazione deve essere fatta attraverso
     un casting!  */
     ge_ptr_1 = (ge_Individual *) input_ptr_1;
     ge_ptr_2 = (ge_Individual *) input_ptr_2;


     /* Si costruiscono le due copie degli individui ai quali applicare
        l'operatore di crossover. Il casting e' necessario poiche' build_
        copy restituisce un tipo Individual. */
     ge_ptr_1 = (ge_Individual *) ge_ptr_1->build_copy();
     ge_ptr_2 = (ge_Individual *) ge_ptr_2->build_copy();

     /* Si memorizzano i puntatori alle copie appena costruite nei parame
        tri di output. */
     output_ptr_1 = ge_ptr_1;
     output_ptr_2 = ge_ptr_2;
     
     

     // Si lancia la monetina ...
     if (flip(prob))
       /* Il crossover viene applicato alle liste di alberi delle copie ap-
          pena costruite. */
       cross(ge_ptr_1->trees_list, ge_ptr_2->trees_list);


     return;
  }

  /*
  ----------------- procedura cross ---------------------------------------
  *** Scritta il:
  Questa procedura implementa l'operazione di crossover, applica l'operato-
  re di crossover alle liste di alberi passate come parametri. Ricordiamo 
  che in questo caso il crossover e' applicato a livello di liste.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void Cross_list::cross(list<class Tree> &list_1, list<class Tree> &list_2)
  {
     
     register list<class Tree>::iterator iter1, iter2;
     int len1, len2, cut1, cut2;

     register list<class Tree> tmp_list;
     
     
     len1 = list_1.size();
     len2 = list_2.size();
     
      
     // Si controlla se uno dei due individui ha una lunghezza pari a 1.
     if ((len1 == 1) || (len2 == 1))
       // In tal caso in crossover non viene effettuato.
       return; 
     
     /* ************** VECCHIA VERSIONE !!! ************* 
     // Si generano in maniera casuale i due punti di taglio.     
     cut1 = rnd(1, list_1.size()); // - 1);
     cut2 = rnd(1, list_2.size()); // - 1);
     ********************/
     
     if (stat) // Crossover a lunghezza fissa
       cut1 = cut2 = rnd(1, list_1.size());
     else give_cut(len1, len2, cut1, cut2, 0); // IMPORTANTE!: DELTA VALE ZERO!!!
     
     // Si controlla se applicare il crossover ordinato:
     if (sorting) { 
       list_1.sort();
       list_2.sort();
    }
    
    /*
    cout<<endl<<"l1: ";
    for (iter1=list_1.begin(); iter1 != list_1.end(); ++iter1) 
       cout<<iter1->label<<" ";
    cout<<endl<<"l2: ";
    for (iter2=list_2.begin(); iter2 != list_2.end(); ++iter2) 
       cout<<iter2->label<<" ";
    */   
     
     
     // Si inizializzano gli iteratori.
     iter1 = list_1.begin();
     iter2 = list_2.begin();

     // Con il primo iteratore si punta al nodo cut1-esimo della lista 1.
     advance(iter1, cut1);

     // Con il secondo iteratore si punta al nodo cut2-esimo della lista 2.
     advance(iter2, cut2);

     /* Si taglia dalla prima lista la parte che si trova dopo cut1 e la si
        memorizza nella lista tmp_list. */
     tmp_list.splice(tmp_list.begin(), list_1, iter1, list_1.end());	 
     
   
     /* Si taglia dalla seconda lista la parte che si trova dopo cut2 e la
        si appende alla lista 1. */
     list_1.splice(list_1.end(), list_2, iter2, list_2.end());

     /* Si appende alla seconda lista quella tagliata dalla prima multilista
        e memorizzata in tmp_list. */
     list_2.splice(list_2.end(), tmp_list);	
        
     
     return;
  }


  /************************************************************************
          Definizione delle procedure per la classe MUTATION
   ***********************************************************************/
  
  /*
  ----------------- procedura Mutation ------------------------------------
  *** Scritta il:
  E' la procedura costruttrice della classe. E' vuota.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  ge_Mutation::ge_Mutation()
  {
   return;
  }

  /*
  ----------------- procedura Mutation ------------------------------------
  *** Scritta il:
  E' la seconda procedura costruttrice della classe. Inizializza il valore
  della probabilita' di applicazione della mutazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  ge_Mutation::ge_Mutation(float prob_value)
  {

    prob = prob_value;

    return;
  }


  /*
  ----------------- procedura apply ---------------------------------------
  *** Scritta il:
  Questa procedura applica l'operazione di mutazione costruendo una copia
  dell'individuo passato come primo parametro e la restituisce come secondo
  parametro. La probabilita' di applicazione della mutazione dipende dalla
  valore probabilita' che e' un attributo della classe.
  *** Ultima modifica: ore 16.00 del 04/04/03
  
  void ge_Mutation::apply(Individual *input_ptr, Individual* &output_ptr)
  {
     Node **node_ptr_ptr;
     char ch;
     int clause, tree_num, i;
     register list<class Tree>::iterator tree_iter; 
     ge_Individual *ge_ptr; /* Questo puntatore serve per le chiamate alle
                               funzioni specifiche del ge. */

     
     /* Si punta l'individuo in input con il puntatore agli oggetti della
        classe ge_Individual. Quest'operazione deve essere fatta attraverso
        un casting!!! 
     ge_ptr = (ge_Individual *) input_ptr;
     
     // Si costruisce una copia dell'individuo da mutare.
     ge_ptr = (ge_Individual *) input_ptr->build_copy();
     
     /* Il puntatore alla copia appena costruita viene memorizzato nel pa-
        rametro di output. 
     output_ptr = ge_ptr;
     
     
     // Si lancia prima di tutto la monetina ...
   //  if (flip(prob))
     {     
       /* Prima di chiamare la procedura di mutazione che muta un albero 
          bisogna sceglierne uno (in maniera random) dalla lista di albe-
          ri degli individui. 
       tree_num = rnd(0, ge_ptr->trees_list.size() - 1);
        
       /* Si scandisce la lista fino ad individuare l'albero scelto.
       for(tree_iter=ge_ptr->trees_list.begin(), i=0; i < tree_num; ++i)
          ++tree_iter;
               ************** PROVA  ********************************
       // Si applica la mutazione all'albero scelto.
       mut(*tree_iter); 
       
       // Si scandisce la lista degli alberi
       for(tree_iter=ge_ptr->trees_list.begin(); tree_iter != ge_ptr->
           trees_list.end(); ++tree_iter)
          if (flip(prob))
            // Si applica la mutazione all'albero corrente.
            mut(*tree_iter);
     }    



     return;
  }

  /*
  ----------------- procedura apply ---------------------------------------
  *** Scritta il:
  E' uguale alla precedente ma NON costruisce la copia, ma applica la muta-
  zione all'unico iundividuo passato come parametro.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void ge_Mutation::apply(Individual* &input_ptr)
  {
     Node **node_ptr_ptr;
     char ch;
     int tree_num, i;
     register list<class Tree>::iterator tree_iter;
     ge_Individual *ge_ptr; /* Questo puntatore serve per le chiaamate al-
                               le funzioni specifiche del ge. */


     /* Si punta l'individuo in input con il puntatore agli oggetti della
        classe ge_Individual. Quest'operazione deve essere fatta attraverso
        un casting!!! */
     ge_ptr = (ge_Individual *) input_ptr;
     
     
     if (prob == 0.0) {
       // ************ MUTAZIONE SINGOLO ALBERO 
     
       // Scelta random dell'albero
       tree_num = rnd(0, ge_ptr->trees_list.size() - 1);
       
       tree_iter = ge_ptr->trees_list.begin();

       // Si avanza il puntatore
       advance(tree_iter, tree_num);

       // Si muta l'albero scelto
       mut(*tree_iter);     
     } else // ************ MUTAZIONE MULTIPLA **************     
         // Si scandisce la lista degli alberi// Si applica la mutazione all'albero scelto.
         for(tree_iter=ge_ptr->trees_list.begin(); 
            tree_iter != ge_ptr->trees_list.end(); tree_iter++)
            // Si lancia la monetina ...     
            if (flip(prob))           
              mut(*tree_iter);
     
        

     return;
  }



   /*
  ----------------- procedura mut -----------------------------------------
  *** Scritta il:
  Questa procedura implementa l'operazione di mutazione sugli alberi di 
  derivazione.
  *** Ultima modifica: ore 16.00 del 04/04/03
  */
  void ge_Mutation::mut(Tree &tree)
  {
     Node **node_ptr_ptr;
     char ch;
     int clause; 
     
     //tree.root->mutation(prob); 
     //return; 
     /* Si sceglie un nodo non terminale dell'albero passato come parame-
        tro. */
     node_ptr_ptr = tree.choose_not_term();

     /* Se non si riesce a scegliere un nodo non terminale dall'individuo,
        esso viene lasciato inalterato. */
     if (node_ptr_ptr == NULL_NODE_PTR)
       return;


     // Si memorizza il simbolo contenuto nel nodo scelto.
     ch = (*node_ptr_ptr)->symbol;
 
     clause = (*node_ptr_ptr)->clause_num;

     // Si elimina la parte sottostante al nodo scelto.
      (*node_ptr_ptr)->del_node(); // PROVA

     
     /* Si genera un nuovo albero il cui nodo radice  contiene il 
        simbolo precedentemente estratto dall'albero per sostituire la par-
        te di albero eliminata. Inoltre, nella chiamata a new_Node si
        specifica il numero della clausola utilizzato dal nodo scelto
        dal individuo di input, cosi' da evitare che la nuova parte di
        albero che viene generata sia uguale a quella da sostituire. */
     (*node_ptr_ptr) = new Node(ch);//, clause);

     return;
  }
 